package SingleLinkedList;

import java.util.List;

public class MySingleLinkedList {
    //把节点定义为内部类
    static class ListNode {
        public int val;
        public ListNode next;//将来next存储的是节点的地址，所以类型应为ListNode

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//链表的头结点

    public void createList() {
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);

        //如何让节点之间关联起来？ node1.next=node2
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;

        this.head=node1;
//        node5.next=null;//这里不用置空，本身默认就是bull
    }

    public void display() {
        ListNode cur=head;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //求链表长度
    public int size() {
        int count=0;
        ListNode cur=head;
        while(cur!=null) {
            count++;
            cur=cur.next;
        }
        return count;
    }

    public void addFirst(int val) {
        ListNode node=new ListNode(val);
        node.next=head;
        head=node;
    }

    public void addLast(int val) {
        ListNode node=new ListNode(val);
        if(head==null) {
            head=node;
            return;
        }
        //找到链表尾巴
        ListNode cur=head;
        while(cur.next!=null) {
            cur=cur.next;
        }
        cur.next=node;
    }

    //要找到index位置的前一个，走index-1步
    //如何连接？node.next=cur.next;cur.next=node;
    //index==0,头插法
    //index==len,尾插法
    //index<0 || index>len
    public void addIndex(int index,int val) {
        ListNode node=new ListNode(val);
        //1.判断index的合法性
        try{
            checkIndexLegal(index);
        }catch(IndexNotLegalException e) {
            e.printStackTrace();
        }
        //2.index==0 || index==size()
        if(index==0) {
            addFirst(val);
            return;
        }
        else if(index==size()) {
            addLast(val);
            return;
        }
        //3.找到index前一个位置
        ListNode cur=findIndexSubOne(index);
        //4.进行连接
        node.next=cur.next;
        cur.next=node;
    }

    public void checkIndexLegal(int index) {
        if(index<0 || index>size()) {
            throw new IndexNotLegalException("index位置不合法");
        }
    }
    private ListNode findIndexSubOne(int index) {
        ListNode node=head;
        for(int i=1;i<index;i++) {
            node=node.next;
        }
        return node;
    }


    public boolean contains(int val) {
        ListNode cur=head;
        while(cur!=null) {
            if(cur.val==val) {
                return true;
            }
            else {
                cur=cur.next;
            }
        }
        return false;
    }

    //删除第一次出现
    public void remove(int val) {
        //如果head为空
        if(head==null) {
            return;
        }
        //删除头结点
        if(head.val==val) {
            head=head.next;
            return;
        }
        //1.要找到要删除节点的前一个节点
        //2.删除
        //3.循环条件是什么？
        ListNode cur=head;
        while(cur.next!=null) {
            if(cur.next.val==val) {
                ListNode del=cur.next;
                cur.next=del.next;
            }
            cur=cur.next;
        }
    }

    public void removeAllKey(int key) {
        //cur代表当前需要删除的节点，prev代表当前需要删除节点的前驱结点
        //if(cur.val==val) prev.next=cur.next; cur=cur.next;
        //else prev=cur;cur=cur.next;
        if(head==null) {
            return;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null) {
            if(cur.val==key) {
                prev.next=cur.next;
                //cur=cur.next;
            }else {
                prev=cur;
                //cur=cur.next;
            }
            cur=cur.next;
        }
        if(head.val==key) {
            head=head.next;
        }
    }

    //
    public void clear() {
//        head=null;
        ListNode cur=head;
        while(cur!=null) {
            ListNode curN=cur.next;
            cur.next=null;
            cur=curN;
        }
        head=null;
    }

}
